package study.datastructure.graph.dijkstra;/**
 * @program: datastructure
 * @author: lcy
 * @create: 2024-06-11 23:18
 */

import java.util.*;

/**
 2024/6/11,
 */

// 使用邻接矩阵实现的Dijkstra算法，使用Map和List表示图
public class Dijkstra {
    public static  int [] dijkstra(Map<Integer, List<Edge>> graph,int startNode,int numOfNodes){
        int [] distances=new int [numOfNodes];
        boolean[] visited=new boolean[numOfNodes];

        //初始化距离数组
        Arrays.fill(distances,Integer.MAX_VALUE);
        distances[startNode] = 0;

        PriorityQueue<Edge> priorityQueue=new PriorityQueue<Edge>(Comparator.comparingInt(e->e.weight));
        priorityQueue.add((new Edge(startNode,startNode,0)));

        while (!priorityQueue.isEmpty()){
            Edge current = priorityQueue.poll();
            Integer currentNode = current.dest;

            if(visited[currentNode]){
                continue;
            }

            visited[currentNode]=true;

            List<Edge> edges = graph.getOrDefault(currentNode, new ArrayList<>());
            for (Edge edge : edges) {
                int newDistances=edge.weight+distances[currentNode];
                if (newDistances<distances[edge.dest]){
                    distances[edge.dest]=newDistances;
                    priorityQueue.add(new Edge(currentNode,edge.dest,edge.weight));
                }
            }

        }
        return distances;

    }

    public static void main(String[] args) {
        Map<Integer, List<Edge>> graph = new HashMap<>();
        int numberOfNodes = 5;

        // 添加边
        addEdge(graph, 0, 1, 10);
        addEdge(graph, 0, 4, 5);
        addEdge(graph, 1, 2, 1);
        addEdge(graph, 1, 4, 2);
        addEdge(graph, 2, 3, 4);
        addEdge(graph, 3, 2, 6);
        addEdge(graph, 4, 1, 3);
        addEdge(graph, 4, 2, 9);
        addEdge(graph, 4, 3, 2);

        int startNode = 0;
        int[] distances = dijkstra(graph, startNode, numberOfNodes);

        System.out.println("Node\tDistance from Node " + startNode);
        for (int i = 0; i < distances.length; i++) {
            if (distances[i] == Integer.MAX_VALUE) {
                System.out.println(i + "\t∞");
            } else {
                System.out.println(i + "\t" + distances[i]);
            }
        }
    }
    // 辅助方法，用于向图中添加边
    private static void addEdge(Map<Integer, List<Edge>> graph, int src, int dest, int weight) {
        graph.computeIfAbsent(src, k-> new ArrayList<Edge>()).add(new Edge(src, dest, weight));
    }
}
